package com.demo.java.OD601_650.OD630;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【找出重复代码(A卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146958487
 */
public class OdMain {
    public static void main(String[] args) {
        // 处理输入
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine(); // 读取第一个字符串
        String str2 = in.nextLine(); // 读取第二个字符串

        // 将字符串转化为字符数组，便于逐字符处理
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        // 初始化dp数组，dp[i][j]表示以s1[i-1]和s2[j-1]为结尾的最长公共子串的长度
        int[][] dp = new int[s1.length + 1][s2.length + 1];
        int maxLen = 0; // 最长公共子串的长度
        int lastPos = 0; // 最后一个公共子串的结束位置

        // 双重循环遍历所有字符，查找最长公共子串
        for (int i = 0; i < s1.length; i++) {
            for (int j = 0; j < s2.length; j++) {
                // 如果字符相等，说明当前字符是公共子串的一部分
                if (s1[i] == s2[j]) {
                    dp[i + 1][j + 1] = dp[i][j] + 1; // 当前公共子串长度加1
                    // 更新最长公共子串的长度和位置
                    if (dp[i + 1][j + 1] > maxLen) {
                        maxLen = dp[i + 1][j + 1];
                        lastPos = i;
                    }
                }
            }
        }

        // 如果没有找到公共子串，输出空字符串
        if (maxLen == 0) {
            System.out.println("");
        } else {
            // 根据maxLen和lastPos输出最长公共子串
            System.out.println(str1.substring(lastPos - maxLen + 1, lastPos + 1));
        }
    }
}